package top.humbleyuan.backtrack;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 16:23
 * @Des 字符串全排列
 */
public class LeetCode_Interview_38 {
    public static void main(String[] args) {
        // 递归
        m1();

        // 回溯剪枝
        m2();
    }

    public static void m1() {
        String str = "123";
        ArrayList<String> list = new ArrayList<>();

        fullPermutation(0, str.toCharArray(), list);

        System.out.println(list);
    }

    /**
     * j表示的是当前需要全排列串的第一个
     * 即核心思想：选取一个当做头，其余全排列
     * @param j
     * @param str
     * @param list
     */
    public static void fullPermutation(int j, char[] str, ArrayList<String> list) {
        // 递归退出
        if(j == str.length - 1) {
            // 当前str中为一种全排列
            String s = String.valueOf(str);

            // 去重
            if(!list.contains(s)) {
                list.add(s);
            }
            return;
        }

        // 从j开始，选取一个为头，后面进行全排列
        for (int i = j; i < str.length; i++) {
            swap(str, i, j);
            // 后面进行全排列,
            fullPermutation(j+1,str,list);
            // 回到上一个状态
            swap(str, i, j);
        }

        int[] nums = {1,2,3};
        String.valueOf(nums);

    }

    // 这里用交换选取头
    public static void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }


    public static void m2() {
        String s = "abc";
        // 利用回溯 + 剪枝
        ArrayList<String> res = new ArrayList<>();
        char[] c = s.toCharArray();
        Arrays.sort(c);

        String cur = "";
        dfs(res, cur, c, new boolean[c.length]);
        System.out.println(res);
    }

    public static void dfs(ArrayList<String> res, String cur, char[] cha, boolean[] visited) {
        if(cur.length() == cha.length) {
            res.add(cur);
            return;
        }

        for(int i = 0 ; i < cha.length ; i++) {
            if(visited[i]) {
                continue;
            }

            if(i > 0 && cha[i] == cha[i - 1] && !visited[i - 1]) {
                continue;
            }

            cur += cha[i];
            visited[i] = true;
            dfs(res, cur, cha, visited);
            cur = cur.substring(0,cur.length() - 1);
            visited[i] = false;
        }
    }
}
